package for_test;

public class SortMethodMerge implements SortMethod{


	@Override
	public int[] sortArray(int[] arr, IntComparator comparator) {
		int[] array = sortArray2(arr, comparator);
		System.arraycopy(array, 0, arr, 0, arr.length);
		return array;
	}
	public int[] sortArray2(int[] arr, IntComparator comparator) {
		if (arr.length <= 1)  
			return arr;  
		int mid = arr.length / 2;  
		int[] left = new int[mid];  
		int[] right = new int[mid + arr.length%2];  

		int j = 0;  
		for (int i = 0; i < arr.length; i++) {  
			if (i < arr.length / 2) {  
				left[i] = arr[i];  
			} else {  
				right[j++] = arr[i];  
			}  
		}  
		return merge(sortArray2(left, comparator), sortArray2(right, comparator), comparator);  

	}

	int[] merge(int[] left, int[] right, IntComparator comparator) {  
		int a = 0, b = 0;  
		int[] merged = new int[left.length + right.length];  
		for (int i = 0; i < left.length + right.length; i++) {  
			if (b < right.length && a < left.length) {  
				if (isSwap(comparator, left[a], right[b]) && b < right.length)  {
					merged[i] = right[b++];  
				} else  {
					merged[i] = left[a++];  
				}
			} else  {
				if (b < right.length)  {
					merged[i] = right[b++];  
				}
				else  {
					merged[i] = left[a++]; 
				}
			}
		}  
		return merged;  
	}  

	protected static boolean isSwap(IntComparator comparator, int i, int j) {
		return comparator.compare(i, j) > 0;
	}


}
